#pragma once
#include <string>
#include <vector>
#include "BinarySerach.h"
#include "AbstractSymbolTable.h"

template<typename Comparable,typename ValueType>
class BSSymbolTable :public AbstractSymbolTable<Comparable, ValueType>
{
public:
	BSSymbolTable();
	~BSSymbolTable();

	void put(const Comparable&obj, const ValueType & value);

	ValueType get(const Comparable&obj);


	int rank(const Comparable&obj);


private:
	BinarySerach<Comparable> algObject;
	std::vector<Comparable> keys;
	std::vector<ValueType> values;
	int realCount;

};


template<typename Comparable, typename ValueType>
BSSymbolTable<Comparable, ValueType>::BSSymbolTable() :realCount(0)
{
}

template<typename Comparable, typename ValueType>
BSSymbolTable<Comparable, ValueType>::~BSSymbolTable()
{
}

template<typename Comparable, typename ValueType>
void BSSymbolTable<Comparable, ValueType>::put(const Comparable&obj, const ValueType & value)
{
	if (keys.size() == 0){
		keys.push_back(obj);
		values.push_back(value);
		return;
	}
		

	int r = algObject.noRecursiveRank(keys, obj);
	//already existed
	if (r < keys.size() && keys[r] == obj)
	{
		values[r] = value;
	}
	else{
		int size = keys.size();
		keys.push_back(keys[size - 1]);
		values.push_back(values[size - 1]);
		for (int i = size; i >= r; --i)
		{
			keys[i] = keys[i - 1];
			values[i] = values[i - 1];

		}
		keys[r] = obj;
		values[r] = value;

	}
	
	for (auto member : keys){
		cout << member << " ";
	}
	cout << endl;
}


template<typename Comparable, typename ValueType>
ValueType BSSymbolTable<Comparable, ValueType>::get(const Comparable&obj)
{
	int r = algObject.noRecursiveRank(keys, obj);
	if (keys[r] == obj)
		return values[r];
	else
	{
		std::cout << "FUCK!" << endl;
		return ValueType();
	}
}

template<typename Comparable, typename ValueType>
int BSSymbolTable<Comparable, ValueType>::rank(const Comparable&obj)
{
	return algObject.noRecursiveRank(keys, obj);
} 